//2009/08/09 03:24:07
//gmark
#include <string>
#include <vector>
#include <map>
#include <queue>
#include <algorithm>

using namespace std;

class HanoiTower
{
public:
    int moves(string pegA, string pegB, string pegC)
    {
        dist.clear();
        vector<int> s, goal;
        s.push_back(encode(pegA));
        s.push_back(encode(pegB));
        s.push_back(encode(pegC));
        char c[] = {'A', 'B', 'C'};
        for (int i=0; i<3; i++)
        {
            int cnt = count(pegA.begin(), pegA.end(), c[i]) + count(pegB.begin(), pegB.end(), c[i]) + count(pegC.begin(), pegC.end(), c[i]);
            goal.push_back(encode(string(cnt, c[i])));
        }
        go(s, dist, 9);
        go(goal, dist2, 10);
        int ans = 1<<30;
        for (map<vector<int>, int>::iterator it = dist.begin(); it != dist.end(); it++)
        {
            if (dist2.count(it->first))
            {
                ans = min(ans, it->second + dist2[it->first]);
            }
        }
        return ans;
    }
private:
    map<vector<int>, int> dist, dist2;
    char c2i(char c)
    {
        return c-'A';
    }
    int encode(string s)
    {
        int cur = 1;
        for (int i=0; i<s.size(); i++)
        {
            cur = 3 * cur + c2i(s[i]);
        }
        return cur;
    }
    void go(vector<int> s, map<vector<int>, int>& dist, int limit)
    {
        dist.clear();
        queue<vector<int> > q;
        q.push(s);
        dist[s] = 0;
        while (!q.empty())
        {
            s = q.front();
            q.pop();
            int d = dist[s];
            if (d > limit) break;

            for (int i=0; i<3; i++)
            {
                for (int j=0; j<3; j++)
                {
                    if (j != i)
                    {
                        vector<int> next = s;
                        next[i] /= 3;
                        next[j] = next[j] * 3 + s[i]%3;
                        if (!dist.count(next))
                        {
                            dist[next] = d + 1;
                            if (d + 1 > limit) break;
                            q.push(next);
                        }
                    }
                }
            }
        }
    }
};
